package foundation.graph;

import java.util.Arrays;
import java.util.Scanner;

/*
    Bellman-Ford算法，解决可以有负权边但是不能有负环(保证最短路存在)的图，单源最短路算法

    松弛操作
    假设源点为A，从A到任意点F的最短距离为distance[F]
    假设从点P出发某条边，去往点S，边权为W
    如果发现，distance[P]+W<distance[S]，也就是通过该边可以让distance[S]变小
    那么就说，P出发的这条边对点S进行了松弛操作

    Bellman-Ford过程
    1，每一轮考察每条边，每条边都尝试进行松弛操作，那么若干点的distance会变小
    2.当某一轮发现不再有松弛操作出现时，算法停止
 */
public class BellmanFord {
    static int MAXN = 1001;
    static int MAXM = 10001;
    static int INF = Integer.MAX_VALUE;
    static int n, m;
    static int[] dist = new int[MAXN]; // dist[x] 存储 1 到x的最短距离
    static int[][] edge = new int[MAXM][3]; // u -> v w


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            edge[i][0] = u;
            edge[i][1] = v;
            edge[i][2] = w;
        }
        int ford = ford();
        System.out.println(ford);
    }


    private static int ford() {
        Arrays.fill(dist, 1, n + 1, INF);
        dist[1] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int u = edge[j][0];
                int v = edge[j][1];
                int w = edge[j][2];
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                }
            }
        }
        if (dist[n] > INF / 2) return -1;
        return dist[n];

    }


}
